package cn.dapeng.window;

import cn.dapeng.utils.BuilderArray;

import java.util.LinkedList;
import java.util.Optional;

/**
 * 假定一个固定大小为W的窗口，依次划过arr
 * 返回每一次滑出状况的最大值
 * 例如：arr=[4,3,5,4,3,3,6,7],W=3
 * 返回:[5,5,5,4,6,7]
 */
public class Code01_SlidingWindowMaxArray {

    /**
     * 效率慢的方式，对数器
     *
     * @param array
     * @param w
     * @return
     */
    public static int[] right(int[] array, int w) {
        if (array == null || array.length == 0 || array.length < w) {
            return null;
        }
        int size = array.length, l = 0, r = w - 1;
        int[] arr = new int[size - w + 1];

        for (int i = l; i < r && r < size; i++) {
            int maxNum = array[l];
            for (int j = l + 1; j <= r; j++) {
                maxNum = Math.max(maxNum, array[j]);
            }
            arr[l] = maxNum;
            l++;
            r++;
        }

        return arr;
    }


    public static int[] slidingV1(int[] array, int w) {
        if (array == null || array.length == 0 || array.length < w) {
            return null;
        }

        int size = array.length, l = 0, r = 1;
        int[] arr = new int[size - w + 1];
        LinkedList<Integer> list = new LinkedList<>();
        list.addLast(0);
        while (l < r && r < size) {

            if ((r - list.peek()) >= w) {
                list.pollFirst();
            }

            while (Optional.ofNullable(list.peekLast()).isPresent() && array[list.peekLast()] <= array[r]) {
                list.removeLast();
            }
            list.addLast(r);

            if (r - l == w - 1) {
                arr[r - w + 1] = array[list.peek()];
                l++;
            }
            r++;
        }
        return arr;
    }

    public static int[] slidingV2(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // qmax 窗口最大值的更新结构
        // 放下标
        LinkedList<Integer> qmax = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int R = 0; R < arr.length; R++) {
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[R]) {
                qmax.pollLast();
            }
            qmax.addLast(R);
            if (qmax.peekFirst() == R - w) {
                qmax.pollFirst();
            }
            if (R >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static int[] slidingV3(int[] num, int w) {

        if (num == null || num.length == 0 || num.length < w) {
            return null;
        }

        LinkedList<Integer> queue = new LinkedList<>();

        int size = num.length, index = 0;
        int[] returnArray = new int[size - w + 1];
        while (index < size) {
            while (!queue.isEmpty() && num[queue.peekLast()] <= num[index]) {
                queue.pollLast();
            }

            queue.addLast(index);

            if (index - queue.peekFirst() == w) {
                queue.pollFirst();
            }

            if (index + 1 >= w) {
                returnArray[index + 1 - w] = num[queue.peekFirst()];
            }
            index++;
        }
        return returnArray;
    }

    public static void main(String[] args) {

        int testTimes = 100_0000;
        int windowWidth = 3;

        for (int i = 0; i < testTimes; i++) {
            int[] array = BuilderArray.builderArray(1000, 50);
            int[] a1 = right(array, windowWidth);
            int[] a2 = slidingV3(array, windowWidth);

            if(!BuilderArray.checkArrayEqual(a1, a2)) {
                BuilderArray.print(array);
                System.out.println("Oops");
                break;
            }
        }

        System.out.printf("共执行%s次", testTimes);

    }
}
